% Ejercicio "De binario y hexadecimal a decimal"
\subsection*{\fbox{\theejercicio} - De binario y hexadecimal a decimal}

Se desea construir una gram\'atica atribuida capaz de hallar el valor decimal de cifras escritas en binario y en hexadecimal. Para diferenciarlas, se utiliza un caracter que precede a la cifra. Si este caracter es una `b' , indica que se trata de una cifra en binario, si es una `x' se trata de una cifra en hexadecimal. Por ejemplo, la cadena de caracteres \verb@"x101"@ tiene un valor decimal de {\tt 257}, y la cadena \verb@"b101"@ tiene un valor decimal de {\tt 5} 

Para simplificar el ejercicio, supondremos que s\'olo se utilizan los d\'{\i}gitos `0' y `1' para la construcci\'on de cualquier cifra, ya sea binaria o hexadecimal.

\begin{enumerate}[1)]
\item Hallar la gram\'atica atribuida basada en la gram\'atica de contexto libre:

{\em S} $\rightarrow$ {\em BC}                                                  \\
{\em C} $\rightarrow$ {\bf 0}{\em C} $|$ {\bf 1}{\em C} $|$ {\bf 0} $|$ {\bf 1} \\
{\em B} $\rightarrow$ {\bf b} $|$ {\bf x}                                       \\

\item Hallar la gram\'atica atribuida basada en la gram\'atica de contexto libre:

{\em S} $\rightarrow$ {\em BC}                                                  \\
{\em C} $\rightarrow$ {\em C}{\bf 0} $|$ {\em C}{\bf 1} $|$ {\bf 0} $|$ {\bf 1} \\
{\em B} $\rightarrow$ {\bf b} $|$ {\bf x}                                       \\

\item Hallar la gram\'atica atribuida basada en la gram\'atica que resulta de la eliminaci\'on de la recursividad izquierda en la gram\'atica del apartado anterior, es decir, a partir de la gram\'atica de contexto libre:

{\em S}\ \ $\rightarrow$ {\em BC}                                             \\
{\em C}\ \ $\rightarrow$ {\bf 0}{\em C'} $|$ {\bf 1}{\em C'}                  \\
{\em C'}   $\rightarrow$ {\bf 0}{\em C'} $|$ {\bf 1}{\em C'} $|\ \varepsilon$ \\
{\em B}\ \ $\rightarrow$ {\bf b} $|$ {\bf x}                                  \\
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

\begin{center}
\begin{tabular}{|lcll|} \hline
        &               &                    &                                   \\
{\em S} & $\rightarrow$ & {\em BC}           & $\{\ C.base = B.base\ \}$         \\
{\em B} & $\rightarrow$ & {\bf b}            & $\{\ B.base = 2\ \}$              \\
{\em B} & $\rightarrow$ & {\bf x}            & $\{\ B.base = 16\ \}$             \\
{\em C} & $\rightarrow$ & {\bf 0}{\em C}$_1$ & $\{\ C.pos = C_1.pos + 1;\ C.valor = C_1.valor;\ C_1.base = C.base\ \}$                  \\
{\em C} & $\rightarrow$ & {\bf 1}{\em C}$_1$ & $\{\ C.pos = C_1.pos + 1;\ C.valor = C.base^{C.pos} + C_1.valor;\ C_1.base = C.base\ \}$ \\
{\em C} & $\rightarrow$ & {\bf 0}            & $\{\ C.pos = 0;\ C.valor = 0\ \}$ \\
{\em C} & $\rightarrow$ & {\bf 1}            & $\{\ C.pos = 0;\ C.valor = 1\ \}$ \\
        &               &                    &                                   \\ \hline
\end{tabular}
\end{center}

Apartado 2)

\begin{center}
\begin{tabular}{|lcll|} \hline
        &               &                    &                                                                   \\
{\em S} & $\rightarrow$ & {\em BC}           & $\{\ C.base = B.base\ \}$                                         \\
{\em B} & $\rightarrow$ & {\bf b}            & $\{\ B.base = 2\ \}$                                              \\
{\em B} & $\rightarrow$ & {\bf x}            & $\{\ B.base = 16\ \}$                                             \\
{\em C} & $\rightarrow$ & {\em C}$_1${\bf 0} & $\{\ C.valor = C.base\cdot C_1.valor;\ C_1.base = C.base\ \}$     \\
{\em C} & $\rightarrow$ & {\em C}$_1${\bf 1} & $\{\ C.valor = C.base\cdot C_1.valor + 1;\ C_1.base = C.base\ \}$ \\
{\em C} & $\rightarrow$ & {\bf 0}            & $\{\ C.valor = 0\ \}$                                             \\
{\em C} & $\rightarrow$ & {\bf 1}            & $\{\ C.valor = 1\ \}$                                             \\
        &               &                    &                                                                   \\ \hline
\end{tabular}
\end{center}

Apartado 3)

\begin{center}
\begin{tabular}{|lcll|} \hline
         &               &                     &                                     \\
{\em S}  & $\rightarrow$ & {\em BC}            & $\{\ C.base = B.base\ \}$           \\
{\em B}  & $\rightarrow$ & {\bf b}             & $\{\ B.base = 2\ \}$                \\
{\em B}  & $\rightarrow$ & {\bf x}             & $\{\ B.base = 16\ \}$               \\
{\em C}  & $\rightarrow$ & {\bf 0}{\em C'}     & $\{\ C.valor = C'.valor;\ C'.base = C.base;\ C.pos = C'.pos + 1\ \}$                             \\
{\em C}  & $\rightarrow$ & {\bf 1}{\em C'}     & $\{\ C.valor = C.base^{C.pos} + C'.valor;\ C'.base = C.base;\ C.pos = C'.pos + 1\ \}$            \\
{\em C'} & $\rightarrow$ & {\bf 0}{\em C'}$_1$ & $\{\ C'.valor = C'_1.valor;\ C'_1.base = C'.base;\ C'.pos = C'_1.pos + 1\ \}$                    \\
{\em C'} & $\rightarrow$ & {\bf 1}{\em C'}$_1$ & $\{\ C'.valor = C'.base^{C'.pos} + C'_1.valor;\ C'_1.base = C'.base;\ C'.pos = C'_1.pos + 1\ \}$ \\
{\em C'} & $\rightarrow$ & $\varepsilon$       & $\{\ C'.pos = 0;\ C'.valor = 0\ \}$ \\
         &               &                     &                                     \\ \hline
\end{tabular}
\end{center}